package ans.p144;

import ans.base.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * #      144
 * 名称   二叉树的前序遍历
 * 链接   https://leetcode-cn.com/problems/binary-tree-preorder-traversal
 * 题解   [1293](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution)
 * 通过率 69.5%
 * 难道   中等
 */

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> ans = new LinkedList<>();

        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop != null) {
                ans.add(pop.val);
            }
            while (pop != null) {
                if (pop.left != null) {
                    ans.add(pop.left.val);
                }
                if (pop.right != null) {
                    stack.push(pop.right);
                }
                pop = pop.left;
            }

        }

        return ans;
    }


    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        preOrder(root, res);
        return res;
    }

    public void preOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }
}